package everyday;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class T1042 {
    int[] answer;

    public int[] gardenNoAdj(int n, int[][] paths) {
        answer = new int[n];
        List<List<Integer>> lists = new ArrayList<>(n);
        for (int i = 0; i < n ; i++) {
            lists.add(new ArrayList<>());
        }
        for (int i = 0; i < paths.length; i++) {
            lists.get(paths[i][0]-1).add(paths[i][1]-1);
            lists.get(paths[i][1]-1).add(paths[i][0]-1);
        }
        for (int i = 0; i <n; i++) {
            int colors = 0;
            for (int d : lists.get(i)) {
                colors = colors | 1 << answer[d];
            }
            int color;
            for (color = 1; color <= 4; color++) {
                if ((colors & 1 << color) == 0){
                    break;
                }
            }
            answer[i]=color;
        }
        return answer;
    }
}
